# -*- coding: utf-8 -*-
# @Time    : 2020/11/8 16:18
# @Author  : DuJiabao
# @File    : power.py
# @Description : this is a program to calculate exponential operation of num.  指数运算

"""
解析：https://leetcode-cn.com/problems/powx-n/solution/
"""

def power1(x, n):
    """
    方法1： 通过递归计算，不断地将指数整除2，减少复杂度
    缺点：空间复杂度较高
    :param x: 底数
    :param n: 指数
    :return: 结果
    """
    if n < 0:
        x = 1 / x
        n = -n
    if n == 0:
        return 1
    if n % 2 == 0:
        return power1(x * x, n // 2)
    else:
        return power1(x * x, n // 2) * x


def power2(x, n):
    """
    方法2：通过迭代的方式，指数可以分解成二进制，即底数多次平方求和的方式。很妙，不占用空间。
    :param x: 底数
    :param n: 指数
    :return: 结果
    """
    if n < 0:
        x = 1 / x
        n = -n
    ans = 1
    x_contribute = x
    while n > 0:
        if n % 2 == 1:  # 遇到1的时候，就乘上去
            ans *= x_contribute
        x_contribute *= x_contribute  # x不断平方 （x, x^2, x^4, x^8, x^16, x^32, x^64）
        n //= 2
    return ans


if __name__ == '__main__':
    print(power1(5, 2))
    print(power2(5, 2))
    print(pow(5, 2))
